package com.lishem.carl._10dp;

/**
 * https://leetcode.cn/problems/min-cost-climbing-stairs/description/
 * <p>
 * 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。
 * <p>
 * 一旦你支付此费用，即可选择向上爬一个或者两个台阶。
 * <p>
 * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
 * <p>
 * 请你计算并返回达到楼梯顶部的最低花费。
 * <p>
 * 1. 确定dp数组（dp table）以及下标的含义
 * <p>
 * dp[i] 表示 到达i层总共的花费
 * <p>
 * 2. 确定递推公式
 * <p>
 * dp[i] = Math.min(dp[i-1]+cost[i-1] , dp[i-2]+cost[i-2]);
 * <p>
 * 3. dp数组如何初始化
 * <p>
 * dp[0] = 0;
 * <p>
 * dp[1] = 0; (题目说我可以选择从0还是1开始，所以1位置也是0)
 * <p>
 * 4. 确定遍历顺序
 * <p>
 * 从前到后
 * <p>
 * 5. 举例推导dp数组
 */
public class _3LetCode746_使用最小花费爬楼梯 {

    public int minCostClimbingStairs(int[] cost) {
        // 算的是楼顶，所以dp数组多申请一个
        int[] dp = new int[cost.length + 1];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[dp.length - 1];
    }

    public static void main(String[] args) {
        _3LetCode746_使用最小花费爬楼梯 sol = new _3LetCode746_使用最小花费爬楼梯();
        int[] arr = new int[]{10, 15, 20};
        System.out.println(sol.minCostClimbingStairs(arr));
    }
}
